
//Limited size hybrid (on the meta predictor), 
//combining gshare and last taken using a 2bit saturating
//counter per branch.


#include <stdio.h>
#include <cassert>
#include <string.h>
#include <inttypes.h>

using namespace std;
#include "cbp3_def.h"
#include "cbp3_framework.h"

// this file includes two sample predictors
// one is a 64 KB gshare conditional predictor
// the other is a 64 KB indirect predictor indexed by (pc ^ history)

// rewind_marked is also used to show how to rewind the reader for multiple runs
// the predictor will use gshare in the first run
// the indirect predictor will be used in the second run

// NOTE: rewind_marked is only provided to help tuning work. the final
// submitted code should only include one run.

#include <map>

#define META_SIZE 18 // Choosing same size as gshare

#define GSHARE_SIZE 18 // 256K 2-bit counters = 64 KB cost
#define IND_SIZE 14    // 16K 32-bit targets  = 64 KB cost

// predictor tables
int8_t   *gtable;
int8_t   *meta_table;
uint32_t *indtable;




// two branch history registers:
// the framework provids real branch results at fetch stage to simplify branch history
// update for predicting later branches. however, they are not available until execution stage
// in a real machine. therefore, you can only use them to update predictors at or after the
// branch is executed.
// in this sample code, we update predictors at retire stage where uops are processed
// in order to enable easy regneration of branch history.

// cost: depending on predictor size
uint32_t brh_fetch;
uint32_t brh_retire;

// count number of runs
//uint32_t runs;

#define PERCEPTRON_HISTORY	59
// old value was 24.

/* number of perceptrons */

#define NUM_PERCEPTRONS		1100
// old value was 163

/* number of bits per weight */

#define PERCEPTRON_BITS		8

/* maximum and minimum weight values */

#define MAX_WEIGHT		((1<<(PERCEPTRON_BITS-1))-1)
#define MIN_WEIGHT		(-(MAX_WEIGHT+1))

/* threshold for training */

#define THETA			((int) (1.93 * PERCEPTRON_HISTORY + 14))

/* size of buffer for keeping 'perceptron_state' for update */

#define NUM_UPDATE_ENTRIES	100

/* perceptron data structure */

typedef struct {
	int	
		/* just a vector of integers */

		weights[PERCEPTRON_HISTORY+1];
} perceptron;

/* 'perceptron_state' - stores the branch prediction and keeps information
 * such as output and history needed for updating the perceptron predictor
 */
typedef struct {

	int
		/* prediction: 1 for taken, 0 for not taken */

		prediction,

		/* perceptron output */

		output;

                 uint32_t
		/* value of the history register yielding this prediction */

		history;	       	

		/* pointer to the perceptron yielding this prediction */

		perceptron *perc;
} perceptron_state;


	/* table of perceptrons */

perceptron perceptrons[NUM_PERCEPTRONS];

perceptron_state 
	/* state for updating perceptron predictor */

	perceptron_state_buf[NUM_UPDATE_ENTRIES];

int 
	/* index of the next "free" perceptron_state */

	perceptron_state_buf_ctr;



/* initialize a single perceptron */

void initialize_perceptron (perceptron *p) {
	int	i;

	for (i=0; i<=PERCEPTRON_HISTORY; i++) p->weights[i] = 0;
}

/* update the perceptron predictor */

void perceptron_update (perceptron_state *u, int taken) {
	int	
		i,
		y, 
		*w;

	uint32_t
		mask, 
		history;


	/* if the output of the perceptron predictor is outside of
	 * the range [-THETA,THETA] *and* the prediction was correct,
	 * then we don't need to adjust the weights
	 */

	if (u->output > THETA)
		y = 1;
	else if (u->output < -THETA)
		y = 0;
	else
		y = 2;
	if (y == 1 && taken) return;
	if (y == 0 && !taken) return;

	/* w is a pointer to the first weight (the bias weight) */

	w = &u->perc->weights[0];

	/* if the branch was taken, increment the bias weight w_0,
	 * else decrement it, with saturating arithmetic
	 */

	if (taken)
		(*w)++;
	else
		(*w)--;
	if (*w > MAX_WEIGHT) *w = MAX_WEIGHT;
	if (*w < MIN_WEIGHT) *w = MIN_WEIGHT;

	/* now w points to the next weight w_1*/

	w++;

	/* get the history that led to this prediction */

	history = u->history;

	/* for each weight and corresponding bit in the history register... */

	for (mask=1,i=0; i<PERCEPTRON_HISTORY; i++,mask<<=1,w++) {

		/* if the i'th bit in the history positively correlates
		 * with this branch outcome, increment the corresponding 
		 * weight, else decrement it, with saturating arithmetic
		 */

		if (!!(history & mask) == taken) {
			(*w)++;
			if (*w > MAX_WEIGHT) *w = MAX_WEIGHT;
		} else {
			(*w)--;
			if (*w < MIN_WEIGHT) *w = MIN_WEIGHT;
		}
	}
}


/* get a prediction in fetch stage*/

perceptron_state *perceptron_dir_lookup_fetch (unsigned int address) {
	int	
		index,
		i,
		output,
		*w;
	uint32_t
		mask;
	perceptron 
		*p;
	perceptron_state
		*u;
          /* get a pointer to the next "free" perceptron_state,
	 * bumping up the pointer (and possibly letting it wrap around) 
	 */


       u = &perceptron_state_buf[perceptron_state_buf_ctr++];
	if (perceptron_state_buf_ctr >= NUM_UPDATE_ENTRIES)
		perceptron_state_buf_ctr = 0;

	/* hash the address to get an index into the table of perceptrons */

	index = address % NUM_PERCEPTRONS;

	/* get pointers to that perceptron and its weights */

	p = &perceptrons[index];
	w = &p->weights[0];

	/* initialize the output to the bias weight, and bump the pointer
	 * to the weights
	 */

	output = *w++;

	/* find the (rest of the) dot product of the history register
	 * and the perceptron weights.  note that, instead of actually
	 * doing the expensive multiplies, we simply add a weight when the
	 * corresponding branch in the history register is taken, or
	 * subtract a weight when the branch is not taken.  this also lets
	 * us use binary instead of bipolar logic to represent the history
	 * register
	 */
	for (mask=1,i=0; i<PERCEPTRON_HISTORY; i++,mask<<=1,w++) {
		if (brh_fetch & mask)
			output += *w;
		else
			output += -*w;
	}
        u->output = output;
	u->perc = p;
        u->history = brh_fetch;
	u->prediction = output >= 0;

	return u;
}

/* get a prediction in retire stage */

perceptron_state *perceptron_dir_lookup_retire (unsigned int address) {
	int	
		index,
		i,
		output,
		*w;
	uint32_t
		mask;
	perceptron 
		*p;
	perceptron_state
		*u;

        /* get a pointer to the next "free" perceptron_state,
	 * bumping up the pointer (and possibly letting it wrap around) 
	 */


        u = &perceptron_state_buf[perceptron_state_buf_ctr++];
	if (perceptron_state_buf_ctr >= NUM_UPDATE_ENTRIES)
		perceptron_state_buf_ctr = 0;

	/* hash the address to get an index into the table of perceptrons */

	index = address % NUM_PERCEPTRONS;

	/* get pointers to that perceptron and its weights */

	p = &perceptrons[index];
	w = &p->weights[0];

	/* initialize the output to the bias weight, and bump the pointer
	 * to the weights
	 */

	output = *w++;

	/* find the (rest of the) dot product of the history register
	 * and the perceptron weights.  note that, instead of actually
	 * doing the expensive multiplies, we simply add a weight when the
	 * corresponding branch in the history register is taken, or
	 * subtract a weight when the branch is not taken.  this also lets
	 * us use binary instead of bipolar logic to represent the history
	 * register
	 */
	for (mask=1,i=0; i<PERCEPTRON_HISTORY; i++,mask<<=1,w++) {
		if (brh_retire & mask)
			output += *w;
		else
			output += -*w;
	}
        u->output = output;
	u->perc = p;
	u->prediction = output >= 0;

	return u;
}

void PredictorInit() {
    //runs = 0;
    gtable = new int8_t[1 << GSHARE_SIZE];
    indtable = new uint32_t[1 << IND_SIZE];
    meta_table = new int8_t[1 << META_SIZE];
    assert(gtable && indtable);

   
}

void PredictorReset() {
    // this function is called before EVERY run
    // it is used to reset predictors and change configurations

    //if (runs == 0)
        printf("Predictor:gshare\nconfig: %i counters, %i KB cost\n", 1 << GSHARE_SIZE, (1 << GSHARE_SIZE) * 2 / 8 / 1024);
    //else
        printf("Predictor:ind\nconfig: %i targets,  %i KB cost\n", 1 << IND_SIZE, (1 << IND_SIZE) * 4 / 1024);

    for (int i = 0; i < (1 << GSHARE_SIZE); i ++)
        gtable[i] = 0;
    for (int i = 0; i < (1 << META_SIZE); i ++)
        meta_table[i] = -1;
    for (int i = 0; i < (1 << IND_SIZE); i ++)
        indtable[i] = 0;

    brh_fetch = 0;
    brh_retire = 0;

 int	i;
    perceptron_state_buf_ctr = 0;
    for (i=0; i<NUM_PERCEPTRONS; i++)
      initialize_perceptron (&perceptrons[i]);

}


void PredictorRunACycle() {
    // get info about what uops are processed at each pipeline stage
    const cbp3_cycle_activity_t *cycle_info = get_cycle_info();

    // make prediction at fetch stage
    for (int i = 0; i < cycle_info->num_fetch; i++) {
        uint32_t fe_ptr = cycle_info->fetch_q[i];
        const cbp3_uop_dynamic_t *uop = &fetch_entry(fe_ptr)->uop;

        if (/* runs == 0 && */uop->type & IS_BR_CONDITIONAL) {
	  uint32_t id = (brh_fetch ^ uop->pc) & ((1 << META_SIZE) - 1);

	  if (meta_table[id] < 0) { //use gshare
	    uint32_t gidx = (brh_fetch ^ uop->pc) & ((1 << GSHARE_SIZE) - 1);
            bool gpred = (gtable[gidx] >= 0);
	    assert(report_pred(fe_ptr, false, gpred));
	  } else { //use perceptron
	    //Get appropriate history:
	    perceptron_state *st = perceptron_dir_lookup_fetch( uop->pc ); // TODO: unsafe conversion?
              // report prediction:
            // you need to provide direction predictions for conditional branches,
            // targets of conditional branches are available at fetch stage.
            // for indirect branches, you need to provide target predictions.
            // you can report multiple predictions for the same branch
            // the framework will use the last reported prediction to calculate 
            // misprediction penalty
           assert(report_pred(fe_ptr, false, st->prediction));		
	  }       
            
              
        }else if (/* runs == 1 && */ uop->type & IS_BR_INDIRECT) {
	  uint32_t id = (brh_fetch ^ uop->pc) & ((1 << META_SIZE) - 1);

	  if (meta_table[id] < 0) { //use gshare
            uint32_t gidx = (brh_fetch ^ uop->pc) & ((1 << IND_SIZE) - 1);
            uint32_t gpred = indtable[gidx];

            assert(report_pred(fe_ptr, false, gpred));
	  } 
        }

        // update fetch branch history
        if (uop->type & IS_BR_CONDITIONAL)
            brh_fetch = (brh_fetch << 1) | (uop->br_taken ? 1 : 0);
        else if (uop_is_branch(uop->type))
            brh_fetch = (brh_fetch << 1) | 1;


    }

    for (int i = 0; i < cycle_info->num_retire; i++) {
        uint32_t rob_ptr = cycle_info->retire_q[i];
        const cbp3_uop_dynamic_t *uop = &rob_entry(rob_ptr)->uop;

        if (/*runs == 0 &&*/ uop->type & IS_BR_CONDITIONAL) { 
            uint32_t gidx = (brh_retire ^ uop->pc) & ((1 << GSHARE_SIZE) - 1);
	    uint32_t id = uop->pc & ((1 << META_SIZE) - 1);

	    perceptron_state *st = perceptron_dir_lookup_retire( uop->pc );
            
	    //update meta predictor
	    bool gpred = (gtable[gidx] >= 0);
	    
	    bool t = uop->br_taken;

	    if (t && gpred && !(st->prediction) && (meta_table[id] > -2)) //Correct, Incorrect	      
	      meta_table[id]--;
	    else 
	      if (t && !gpred && (st->prediction) && (meta_table[id] < 1)) //Incorrect, Correct
		meta_table[id]++;
	      else
		if (!t && gpred && !(st->prediction) && (meta_table[id] < 1)) //Incorrect, Correct
		  meta_table[id]++;
	        else
		  if (!t && !gpred && (st->prediction) && (meta_table[id] > -2)) //Correct, Incorrect
		    meta_table[id]--;
	    


            // update gshare predictor
            
            if (t && gtable[gidx] < 1)
                gtable[gidx] ++;
            else if (!t && gtable[gidx] > -2)
                gtable[gidx] --;

	    perceptron_update( st, uop->br_taken );

	    

        }else if (/*runs == 1 &&*/ uop->type & IS_BR_INDIRECT) {
            uint32_t gidx = (brh_retire ^ uop->pc) & ((1 << IND_SIZE) - 1);
            indtable[gidx] = uop->br_target;
	    

        }

	


	


        // update retire branch history
        if (uop->type & IS_BR_CONDITIONAL)
            brh_retire = (brh_retire << 1) | (uop->br_taken ? 1 : 0);
        else if (uop_is_branch(uop->type))
            brh_retire = (brh_retire << 1) | 1;


      


    }
}

void PredictorRunEnd() {
/*
    runs ++;
    if (runs < 2) // set rewind_marked to indicate that we want more runs
        rewind_marked = true;
*/
}

void PredictorExit() {
    delete [] gtable;
    delete [] indtable;
    delete [] meta_table;

}
